﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm
{
    class SimplifiedSudoku
    {
        private const int N = 9;
        private const int UNASSIGNED = 0;

        /** The model */
        protected int[,] model;

        public SimplifiedSudoku()
        {
            CreateModel();
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            for (int row = 0; row < N; row++)
            {
                for (int col = 0; col < N; col++)
                {
                    sb.AppendFormat("{0} ", model[row, col] == UNASSIGNED ? " " : model[row, col].ToString());
                }
                sb.AppendLine();
            }

            return sb.ToString();

        }

        /** Creates the model and sets up the initial situation */
        protected void CreateModel()
        {
            model = new int[N, N];

            // Clear all cells
            for (int row = 0; row < N; row++)
            {
                for (int col = 0; col < N; col++)
                {
                    model[row, col] = UNASSIGNED;
                }
            }

            // Create the initial situation
            model[0, 0] = 9;
            model[0, 4] = 2;
            model[0, 6] = 7;
            model[0, 7] = 5;

            model[1, 0] = 6;
            model[1, 4] = 5;
            model[1, 7] = 4;

            model[2, 1] = 2;
            model[2, 3] = 4;
            model[2, 7] = 1;

            model[3, 0] = 2;
            model[3, 2] = 8;

            model[4, 1] = 7;
            model[4, 3] = 5;
            model[4, 5] = 9;
            model[4, 7] = 6;

            model[5, 6] = 4;
            model[5, 8] = 1;

            model[6, 1] = 1;
            model[6, 5] = 5;
            model[6, 7] = 8;

            model[7, 1] = 9;
            model[7, 4] = 7;
            model[7, 8] = 4;

            model[8, 1] = 8;
            model[8, 2] = 2;
            model[8, 4] = 4;
            model[8, 8] = 6;
        }


        public bool Solve()
        {
            return SolveSudoku(model);
        }

        /* Takes a partially filled-in grid and attempts to assign values to
          all unassigned locations in such a way to meet the requirements
          for Sudoku solution (non-duplication across rows, columns, and boxes) */
        private bool SolveSudoku(int[,] grid)
        {
            int row = 0;
            int col = 0;

            // If there is no unassigned location, we are done
            if (!FindUnassignedLocation(grid, ref row, ref col))
                return true; // success!

            // consider digits 1 to 9
            for (int num = 1; num <= N; num++)
            {
                // if looks promising
                if (isSafe(grid, row, col, num))
                {
                    // make tentative assignment
                    grid[row, col] = num;

                    // return, if success, yay!
                    if (SolveSudoku(grid))
                    {
                        return true;
                    }
                    else
                    {
                        // failure, unmake & try again
                        grid[row, col] = UNASSIGNED;
                    }
                }
            }
            return false; // this triggers backtracking
        }

        /* Searches the grid to find an entry that is still unassigned. If
           found, the reference parameters row, col will be set the location
           that is unassigned, and true is returned. If no unassigned entries
           remain, false is returned. */
        private bool FindUnassignedLocation(int[,] grid, ref int row, ref int col)
        {
            for (row = 0; row < N; row++)
            {
                for (col = 0; col < N; col++)
                {
                    if (grid[row, col] == UNASSIGNED)
                    {
                        return true;
                    }
                }
            }
            return false;
        }

        /* Returns a boolean which indicates whether any assigned entry
           in the specified row matches the given number. */
        private bool UsedInRow(int[,] grid, int row, int num)
        {
            for (int col = 0; col < N; col++)
            {
                if (grid[row, col] == num)
                {
                    return true;
                }
            }
            return false;
        }

        /* Returns a boolean which indicates whether any assigned entry
           in the specified column matches the given number. */
        private bool UsedInCol(int[,] grid, int col, int num)
        {
            for (int row = 0; row < N; row++)
            {
                if (grid[row, col] == num)
                {
                    return true;
                }
            }
            return false;
        }

        /* Returns a boolean which indicates whether any assigned entry
           within the specified 3x3 box matches the given number. */
        private bool UsedInBox(int[,] grid, int boxStartRow, int boxStartCol, int num)
        {
            for (int row = 0; row < 3; row++)
            {
                for (int col = 0; col < 3; col++)
                {
                    if (grid[row + boxStartRow, col + boxStartCol] == num)
                    {
                        return true;
                    }
                }
            }
            return false;
        }

        /* Returns a boolean which indicates whether it will be legal to assign
           num to the given row,col location. */
        private bool isSafe(int[,] grid, int row, int col, int num)
        {
            /* Check if 'num' is not already placed in current row,
               current column and current 3x3 box */
            return !UsedInRow(grid, row, num) &&
                   !UsedInCol(grid, col, num) &&
                   !UsedInBox(grid, row - row % 3, col - col % 3, num);
        }

    }
}
